package com.leetcodehot.problems;

public class problems2096 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 做法一：
     * 先找到最近公共祖先节点，然后对于startValue到祖先就都选U，从公共祖先节点到destValue就是RL
     */
    private TreeNode start;
    private TreeNode dest;

    private TreeNode dfs(TreeNode root, int startValue, int destValue) {
        if (root == null || root.val == startValue || root.val == destValue) {
            return root;
        }
        TreeNode left = dfs(root.left, startValue, destValue);
        TreeNode right = dfs(root.right, startValue, destValue);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    StringBuilder str = new StringBuilder();
    String ans = "";

    public String getDirections(TreeNode root, int startValue, int destValue) {
        TreeNode parent = dfs(root, startValue, destValue);
        TreeNode node = parent;
        dfsFind(parent, startValue);//多少个U(直接算L or R的数量)
        ans = ans.replace('L', 'U');
        ans = ans.replace('R', 'U');
        str.delete(0, str.length());
        dfsFind(parent, destValue);//L or R
        return ans;
    }

    private boolean dfsFind(TreeNode root, int val) {
        if (root == null) return false;
        if (root.val == val) {
            ans += str.toString();
            return true;
        }
        str.append("L");
        if (dfsFind(root.left, val)) {
            return true;
        }
        str.deleteCharAt(str.length() - 1);
        str.append("R");
        if (dfsFind(root.right, val)) {
            return true;
        }
        str.deleteCharAt(str.length() - 1);
        return false;
    }
}
